package leetcode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-29 13:42
 **/
public class LeetCode1995 {

    //hash表优化
    public int countQuadruplets(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();

        int count = 0;
        int n = nums.length;
        //第一层从右往左遍历,便利前将右边的元素添加到map中
        for (int b = n - 3; b >= 1; --b) {
            for (int d = b + 2; d < n; ++d) {
                int num = nums[d] - nums[b + 1];

                map.put(num, map.getOrDefault(num, 0) + 1);
            }
            for (int a = 0; a < b; ++a) {
                int num = nums[a] + nums[b];
                count += map.getOrDefault(num, 0);
            }
        }
        return count;
    }

    //hash表
    /*public int countQuadruplets(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();

        int count = 0;
        int n = nums.length;
        //第一层从右往左遍历,便利前将右边的元素添加到map中
        for (int i = n - 2; i >= 2; --i) {
            map.put(nums[i + 1], map.getOrDefault(nums[i + 1], 0) + 1);
            for (int j = 0; j < i - 1; ++j) {
                for (int k = j + 1; k < i; ++k) {
                    int sum = nums[i] + nums[j] + nums[k];
                    if (map.containsKey(sum)) {
                        count += map.get(sum);
                    }
                }
            }
        }
        return count;
    }*/

    //暴力
    /*public int countQuadruplets(int[] nums) {
        int count = 0;
        int n = nums.length;
        for (int i = 3; i < n; ++i) {
            for (int j = 0; j <= i - 3; ++j) {
                for (int k = j + 1; k <= i - 2; ++k) {
                    for (int h = k + 1; h <= i - 1; ++h) {
                        if (nums[j] + nums[k] + nums[h] == nums[i]) {
                            ++count;
                        }
                    }
                }
            }
        }

        return count;
    }*/


}
